學習筆記►機器學習基石

Machine Learning Foundations - L2 Notes(下)

Contents

  1. 1. 前提
  2. 2. 三 Guarantee of PLA
    1. 2.1. Linear Separability
    2. 2.2. 與目標做比較
    3. 2.3. 小練習
  3. 3. 四 Non-Separable Data
    1. 3.1. PLA 的問題
    2. 3.2. Noise
    3. 3.3. Pocket Algorithm
  4. 4. 補充

前提

延續上次沒打完的…

三 Guarantee of PLA

Linear Separability

要如何知道資料是否能用一條線來劃分？這邊提到一個性質 Linear Separability 線性可分。

2-3-1

那問題來了，當有這性質時，PLA 就會停下來了嗎？

與目標做比較

假設 $w_f$ 是完美正確的，那就代表它不會出錯。也就是其 w 和 x 做內積後的結果(正負)會與 y 相同。

就可推得圖片內第一段的式子，有了這個前提之後，要來比較我們找的 $w_t$ 和 $w_f$。
有 min 那項為離線最近的點，但它的分類仍為正確的，所以會大於 0。

要比較兩個向量，可以把它們做 內積，值越大，代表它們夾角 越小，也就是越接近。
透過圖中的推導可以發現(注意顏色及其對應的式子)， $w_t$ 和 $w_f$ 做內積的值會越來越大，也就是越來越接近。

2-3-2

而使得內積的值變大，也有可能是因為 $w$ 的長度變長，而不是夾角變小啊，那怎辦呢？

這邊重提一個重點，PLA 是只有在 出錯 時才會進行修正。而在出錯時，與結果符號不相符，會有下圖中 藍色 的數學式子。

經過一番推導可以發現，實際上影響 $w_t$ 長度增加的關鍵會是 ${\Vert{y_{n(t)}x_{n(t)}}\Vert}^2$ 此項是正的。成長的速度 不會 這麼快。

2-3-3

經過 $T$ 次錯誤修正後

$\frac {w^T_f}{\Vert{w_f}\Vert} \frac {w_T}{\Vert{w_T}\Vert}$

這兩個單位向量做內積，就可得到它們之間的餘弦(cos)，而 $T$ 是次數，也就代表了它們越來越接近。那當然也不是無止境的接近，cos 的最大值為 1。
( $\overrightarrow{A} \cdot \overrightarrow{B} = \vert{A}\vert\vert{B}\vert cos\theta$ )

最後我們可以知道在 Data Linear Separability 的前提下，PLA 最後會停下來。

小練習

呼應剛剛所講:

2-3-4

至於為甚麼答案是這樣…..到底怎算的阿Orz

四 Non-Separable Data

PLA 的問題

實際上我們要知道 Data 是不是 Linear Separability ，我們需要知道它的 $w_f$ ，但顯然得我們不知道。就算假設我們知道它是 Linear Separability ，也無從得知 PLA 何時會停止。

Noise

現在有些點是不合理的，比如資料錯誤等等，這時候就是所謂的 雜訊(Noise) 。此時我們無法找到一條線來分類，使得在所有點的清況下都不出錯。
剛說到 PLA 會在沒有錯誤的時候停止，代表找到一條 $w_g$ 。 我們在這邊只好退而求其次，將所謂的 最好 的線定義為出錯次數 最少 的。結果這樣一個做法是個 NP-hard 的問題，所以也沒辦法有效率的解決。
所以我們要用的是 Pocket Algorithm 。

2-4-1

Pocket Algorithm

在不是 Linear Separability 的情況下，可以考慮 Pocket Algorithm。
PLA 的一種變形，用比較隨機的方式去找出錯誤的點，然後修正它，接著將它與之前找到的 $w_t$ 做比較，看哪條比較好就留下哪條。(做了足夠的檢查後就停止)

2-4-2

補充

關於 PLA 和 pocket 的寫法 : http://wizmann.tk/ml-foundations-pla.html
網路上也有蠻多關於它們的資訊就是了。